package org.example.sword2offer.primary;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @author: lynn
 * @Descript:  设计调度算法使规定时间内执行任务最多--贪心策略
 *  https://blog.csdn.net/u014106644/article/details/83213481
 * @date: 2021/6/27 18:38
 * @version: 1.0
 */
public class Q73_MaxExecuteJobbyTime {



    static class TimeComparator implements Comparator<Time> {
        @Override
        public int compare(Time o1, Time o2) {
            return o1.end - o2.end;
        }
    }

    /**
     *  可以使用贪心策略，先选取第一个任务，第一个任务应该具有什么特征才能使总任务数最多。
     *  第一次，想的是任务的起始时间最小的，尽管起始时间可能最小，然而可能任务结束时间也晚，
     *  这样中间一段时间可能执行更多的任务，因此不对。其实应该按照任务的结束时间最小来选取，
     *  当选取第一个任务为结束时间最小时，后面可以剩余更多时间来选取其他任务，其实当选取一个任务时，
     *  相当于更新start=选取任务的结束时间，这样便转换为一个子问题
     */

    public static int maxTask(Time[] tt, int start, int end){ //fixme 设计调度算法使规定时间内执行任务最多--贪心策略
        Arrays.sort(tt,  (o1,o2)->{return o1.end-o2.end;});//fixme 以结束时间升序排序,list是collections.sort
        System.out.println(Arrays.toString(tt));
        int num = 0;
        for(int i=0; i<tt.length; i++){//fixme 核心算法
            if(tt[i].start>=start && tt[i].end<=end){//fixme 满足条件，则先执行，start更新为执行任务的结束时间
                num++;
                start = tt[i].end;//fixme 容易错
            }
        }
        return num;
    }
    static class Time{
        int start;int end;
        public Time(int start, int end){
            this.start = start;this.end = end;
        }
        @Override
        public String toString() {
            return "[" + start + "," + end + "]";// TODO Auto-generated method stub
        }
    }
    public static void main(String[] args) {
        Time[] tt = new Time[]{new Time(1,3), new Time(1,9), new Time(2,4), new Time(3,6), new Time(6,7), new Time(7,8)};
        System.out.println(maxTask(tt, 0, 10));
    }
}
